Logical Equivalences
- Implication Equivalence:
- Biconditional Equivalence:
- Identity Law:
- Identity Law:
- Complement Law:
- Complement Law:
- Idempotent Law:
- Idempotent Law:
- Double Negation Law:
- Associative Law:
- Distributive Law:
- Distributive Law:
- De Morgan’s Law:
- De Morgan’s Law:
- Bi-implication Equivalence:
- Adjacency Law:
- Simplification Law:
- Contrapositive Equivalence:
Predicate Logic
- De Morgan’s Law for Universal Quantifier:
- De Morgan’s Law for Existential Quantifier:
- Restricted Universal:
- Restricted Existential:
Set Theory
- Complement:
- Difference:
- De Morgan’s Law:
- De Morgan’s Law:
- Distributive Law:
- Cardinality of a Union (Two Sets):
- Cardinality of a Union (Three Sets):
- Cardinality of a Set Difference:
- Cardinality of a Cartesian Product:
- Intersection of Cartesian Products:
- Intersection of Power Sets:
Proofs and Number Theory
- Definition of an Odd Integer:
- Definition of an Even Integer:
- Sum of First Integers:
- Sum of First Squares:
- Sum of a Geometric Series:
- Fibonacci Recurrence Relation:
- Binet’s Formula:
- Sum of First Odd-Indexed Fibonacci Numbers:
- Bernoulli’s Inequality:
Combinatorics
- Ordered Arrangement with Repetition:
- Ordered Arrangement without Repetition (Permutation):
- Permutation of n distinct items:
- Unordered Arrangement without Repetition (Combination):
- Partitioning into Unordered Groups:
- Permutations with Repetition (Multinomial Coefficient):
- Coefficient of in :
- Coefficient of in :
- Unordered Arrangement with Repetition (Stars and Bars):
- Solutions to for :
- Complementary Counting:
Recurrence Relations
- Arithmetic Progression:
- Geometric Progression:
- Second-Order Recurrence General Solution (Distinct Roots ):
- Second-Order Recurrence General Solution (Repeated Root ):
Relations and Graph Theory
- Total Number of Binary Relations on Elements:
- Number of Reflexive Relations on Elements:
- Number of Irreflexive Relations on Elements:
- Number of Symmetric Relations on Elements:
- Number of Asymmetric Relations on Elements:
- Number of Anti-symmetric Relations on Elements:
- Number of Linear Orders on Elements:
- Asymmetric Relation Equivalence: Asymmetric Anti-symmetric Irreflexive
- Non-strict from Strict Order:
- Handshaking Lemma: (the sum of all degrees equals twice the number of edges)
- Number of Edges in Complete Graph :
- Degree of Vertices in : Each vertex has degree
- Degree of Vertices in : Each vertex has degree 2
- Number of Edges in :
- Number of Edges in Complete Bipartite Graph :
- Characteristic Property of Trees: A connected graph with vertices is a tree if and only if it has exactly edges
- Number of Edges in a Forest: A forest with vertices and components has exactly edges
- Number of Possible Simple Graphs of Order : (each potential edge can be present or absent)
- Number of Possible Bipartite Graphs with Sets and : (each potential edge between sets can be present or absent)
Eulerian and Hamiltonian Graphs
- Euler Cycle Condition: A non-trivial connected graph is Eulerian if and only if every vertex has even degree
- Euler Path Condition: A connected graph has an Euler path if and only if it has exactly zero or exactly two vertices with odd degree
- Complete Graph Eulerian: is Eulerian if and only if is odd
- Complete Bipartite Graph Eulerian: is Eulerian if and only if both and are even
- Complete Bipartite Graph Hamiltonian: is Hamiltonian if and only if
- Dirac’s Theorem (Sufficient Condition for Hamiltonian): Let be a simple graph with vertices. If for every vertex , then is Hamiltonian
- Ore’s Theorem (Sufficient Condition for Hamiltonian): Let be a simple graph with vertices. If for every pair of non-adjacent vertices and , then is Hamiltonian
Planar Graphs and Colourings
- Euler’s Formula (Planar Graphs): , where = vertices, = edges, = faces (including exterior face)
- Edge Bound for Planar Graphs: If is a connected planar graph with , then
- Edge Bound for Bipartite Planar Graphs: If is a connected bipartite planar graph with , then
- Face-Edge Inequality (General): (each face has at least 3 edges, each edge borders at most 2 faces)
- Face-Edge Inequality (Bipartite): (bipartite graphs have no triangles, so each face has at least 4 edges)
- Chromatic Number of Complete Graph:
- Chromatic Number of Null Graph: (graph with no edges)
- Chromatic Number of Bipartite Graph: for any non-trivial bipartite graph
- Chromatic Number of Odd Cycle:
- Chromatic Number of Even Cycle:
- Four Colour Theorem: for any planar graph
- Kuratowski’s Theorem: A graph is planar if and only if it does not contain a subgraph that is a subdivision of or